This is a dictionary of algorithms, algorithmic techniques, data structures, archetypical problems, and related definitions. Algorithms include common functions, such as Ackermann's function. Problems include traveling salesman and Byzantine generals. Some entries have links to implementations and more information. Index pages list entries by area, for instance, sorting, searching, or graphs, and by type, for example, algorithms or data structures. The two-level index has a total download 1/20 as big as this page.

Don't use this site to cheat. Teachers, contact me if I can help.

To define or correct terms, please contact Paul E. Black. We need help in automata theory, combinatorics, parallel or randomized algorithms, heuristics, and quantum computing. We do not include algorithms particular to business data processing, communications, operating systems or distributed algorithms, programming languages, AI, graphics, or numerical analysis: it is tough enough covering "general" algorithms and data structures. However, if you want to tackle one of these areas, we'll consider including them.

Some terms with a leading variable, such as n-way, m-dimensional, or p-branching, are under k-. You may find terms dealing with hardware, the computer industry, slang, etc., in the Free On-Line Dictionary Of Computing or in A Glossary of Computer Oriented Abbreviations and Acronyms.

To look up words or phrases, enter them in the box, then click the button. To look up algorithms by example, use AlgoVista.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

We thank those who contributed definitions as well as many others who offered suggestions and corrections.

Here are some references on algorithms and data structures.

[CLR90] Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, MIT Press, 1990.

[HS83] Fundamentals of Data Structures, Ellis Horowitz and Sartaj Sahni, Computer Science Press, 1983.

Algorithms in C, Robert Sedgewick, Addison-Wesley, 1997.

Handbook of Algorithms and Data Structures -- in Pascal and C, G. Gonnet and R. Baeza-Yates, Addison-Wesley, 1991.

The Stony Brook Algorithm Repository, which has algorithms organized by type, succinct, illustrated definitions, and ratings of sites with implementations.

Data Structures and Algorithms is a wonderful site with illustrations, explanations, analysis, and code taking the student from arrays and lists through trees, graphs, and intractable problems.

Bibliography

[AS98] Pankaj K. Agarwal and Micha Sharir, Efficient Algorithms for Geometric Optimization, ACM Computing Surveys, 30(4):412-458, December 1998.

[ATCH99] Algorithms and Theory of Computation Handbook, Mikhail J. Atallah, ed., CRC Press LLC, 1999.

[GCG92] P. Gupta, P. P. Chakrabarti, and S. Ghose, The Towers of Hanoi: Generalizations, Specializations, and Algorithms, Intern. J. Computer Math., 46:149-161, Gordon and Breach Science Publishers S.A., 1992.

[GG98] Volker Gaede and Oliver Günther, Multidimensional Access Methods, ACM Computing Surveys, 30(2):170-231, June 1998.

[Hirv01] Mika Hirvensalo, Quantum Computing, Springer-Verlag, 2001.

[Knuth98] Donald E. Knuth, The Art of Computer Programming, Addison-Wesley, volumes 1, 2, and 3, 3^rd edition, 1998.

[Leda98] LEDA (accessed 4 December 2002).

[Stand98] Thomas Standish, Data Structures in Java, Addison-Wesley, 1998.

[Sund98] Daniel M. Sunday, A Very Fast Substring Search Algorithm, Communications of the ACM, 33(8):132-142, August 1998.

[Vitt01] Jeffrey Scott Vitter, External Memory Algorithms and Data Structures: Dealing with Massive Data, ACM Computing Surveys, 33(2):209-271, June 2001.

[Wier98] Roel Wieringa, A Survey of Structured and Object-Oriented Software Specification Methods and Techniques, ACM Computing Surveys, 30(4):459-527, December 1998.

The FOLDOC style guide.

This dictionary is an example for Problem Set 4 of Software Engineering of Innovative Web Services.

Robots, please index all term pages, including spelling variants.

This page's URL is http://www.nist.gov/dads/